// 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
//用栈的方法
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list =  new ArrayList<>();
        Stack<TreeNode>stack = new Stack<>();
        TreeNode e = root;
        while(!stack.isEmpty()||e!=null)
        {
            if(e!=null)
            {
                stack.push(e);
                e = e.left;
            }
            else{
                TreeNode tmp = stack.pop();
                list.add(tmp.val);
                e = tmp.right;
            }
        }
        return list;
    }    
}